package th.retrofit.lib;

/**
 * https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
 * 给定一个二叉树
 *
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *
 * 初始状态下，所有 next 指针都被设置为 NULL。
 */
public class Solution117 {

    public Node connect1(Node root) {
        if (root == null) return root;
        Node lineStart = root;
        Node pre = lineStart;
        while (pre != null && (pre.left != null || pre.right != null)) {
            Node right;
            if (pre.left != null && pre.right != null) {
                lineStart = pre.left;
                pre.left.next = pre.right;
                right = pre.right;
            } else if (pre.left != null) {
                lineStart = pre.left;
                right = lineStart;
            } else {
                lineStart = pre.right;
                right = lineStart;
            }
            Node next = pre.next;
            while (next != null) {
                if (next.left != null && next.right != null) {
                    next.left.next = next.right;
                    right.next = next.left;
                    right = next.right;
                } else if (next.left != null) {
                    right.next = next.left;
                    right = next.left;
                } else if (next.right != null) {
                    right.next = next.right;
                    right = next.right;
                }
                next = next.next;
            }
            pre = lineStart;
            while (pre != null && pre.left == null && pre.right == null) {
                pre = pre.next;
            }
        }
        return root;
    }

    public Node connect(Node root) {
        if (root == null) return root;
        Node head = findNext(root);
        connect(head);
        return root;
    }

    public Node findNext(Node root) {
        if (root == null) return root;
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
            root.right.next = findNext(root.next);
            return root.left;
        } else if (root.left != null) {
            root.left.next = findNext(root.next);
            return root.left;
        } else if (root.right != null) {
            root.right.next = findNext(root.next);
            return root.right;
        }
        return findNext(root.next);
    }

    public static void main(String[] args) {
        Node root = Node.array2Tree(2,1,3,0,7,9,1,2,null,1,0,null,null,8,8,null,null,null,null,7);
        new Solution117().connect(root);
        System.out.println(root);
    }

}
